package everyday;

/**
 * @author zhangmin
 * @create 2022-05-06 13:28
 * 剑指 Offer 51. 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 *
 * 思路：
 * 用归并排序的过程中记录逆序对
 */
public class reversePairs_offer51 {
    int[] temp;
    int merge(int[] nums,int left,int right){
        if(left>=right) return 0;
        int mid=left+(right-left)/2;
        int count=merge(nums,left,mid)+merge(nums,mid+1,right);
        //合并左右两部分，需要先复制出来
        for (int k = left; k <= right; k++) {
            temp[k]=nums[k];
        }
        int i=left,j=mid+1;
        for (int k = left; k <= right; k++) {
            if (i==mid+1){
                //左边合并完了
                nums[k]=temp[j++];
            }else if (j==right+1){
                nums[k]=temp[i++];
            }else if (temp[i]<=temp[j]){
                //不会产生逆序对
                nums[k]=temp[i++];
            }else {
                //会产生逆序对,且j和从i到mid的元素都成了逆序对
                nums[k]=temp[j++];
                count+=(mid-i+1);
            }
        }
        return count;
    }
    public int reversePairs(int[] nums) {
        int n=nums.length;
        temp=new int[n];
        return merge(nums,0,n-1);
    }
}
